package com.datastructure.test.serializablebinarytree;

import java.util.ArrayList;
import java.util.Arrays;

public class SerializableBinaryTree {

    public static void main(String[] args) {
        SerializableBinaryTree serializableBinaryTree = new SerializableBinaryTree();
        TreeNode treeNode = new TreeNode(1);
        treeNode.left=new TreeNode(2);
        treeNode.right=new TreeNode(3);
        treeNode.right.left=new TreeNode(6);
        treeNode.right.right=new TreeNode(7);
        String serialize = serializableBinaryTree.Serialize(treeNode);
        TreeNode deserialize = serializableBinaryTree.Deserialize(serialize);
        System.out.println(deserialize);
    }

    String Serialize(TreeNode root) {
        if(root==null){
            return null;
        }
        ArrayList<Integer> list = new ArrayList<>();
        preOrder(root,list);
        String[] preString = new String[list.size()];
        for (int i = 0; i < list.size(); i++) {
            preString[i]=String.valueOf(list.get(i));
        }
        String preJoin = String.join(" ", preString);
        list.clear();
        inOrder(root,list);
        for (int i = 0; i < list.size(); i++) {
            preString[i]=String.valueOf(list.get(i));
        }
        String inJoin = String.join(" ", preString);
        return preJoin+"  "+inJoin;
    }

    TreeNode Deserialize(String str) {
        if(str==null){
            return null;
        }
        String[] s = str.split(" {2}");
        String s1 = s[0];
        String s2 = s[1];
        String[] split = s1.split(" ");
        int[] pre = new int[split.length];
        for (int i = 0; i < split.length; i++) {
            pre[i]=Integer.parseInt(split[i]);
        }
        String[] split1 = s2.split(" ");
        int[] in = new int[split1.length];
        for (int j = 0; j < split1.length; j++) {
            in[j]=Integer.parseInt(split1[j]);
        }
        return constructBinaryTree(pre,in);
    }

    public TreeNode constructBinaryTree(int[] pre,int[] in){
        if(pre.length==0||in.length==0){
            return null;
        }
        TreeNode root = new TreeNode(pre[0]);
        for (int i = 0; i < in.length; i++) {
            if(in[i]==pre[0]){
                root.left=constructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
                root.right=constructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));
            }
        }
        return root;
    }


    public void preOrder(TreeNode root, ArrayList<Integer> list){
        if(root!=null){
            list.add(root.val);
        } else {
            return;
        }
        preOrder(root.left,list);
        preOrder(root.right,list);
    }

    public void inOrder(TreeNode root,ArrayList<Integer> list){
        if(root==null){
            return;
        }
        inOrder(root.left,list);
        list.add(root.val);
        inOrder(root.right,list);
    }
}

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
